package com.darrenchan.leetcode;

import java.util.Arrays;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-04-20 00:35
 */
public class QLint382 {
    public int triangleCount(int[] S) {
        if(S == null || S.length < 3) {
            return 0;
        }

        Arrays.sort(S);
        int cnt = 0;
        for (int i = S.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while(left < right) {
                if(S[left] + S[right] > S[i]) {
                    cnt += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }

        return cnt;
    }
}
